package _0_climbingStairsgo

import "fmt"

/**
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

爬楼梯经典题目

核心思想：当前状态由前面有限状态推导（状态转移）
dp[n] = dp[n-1] + dp[n-2]

步骤 1：确定 dp 数组含义
	dp[i] 表示到第 i 阶楼梯的走法数
步骤 2：确定状态转移方程（重点）
	dp[i] = dp[i-1] + dp[i-2]
	步骤 3：初始化 dp 数组
	dp[1]=1
	dp[2]=2
步骤 4：遍历顺序
	for i := 2; i <= n; i++ {
		...
	}
步骤 5：（可选）空间优化
	大多数斐波那契式 DP 可以压缩空间：
	prev, curr := dp[i-2], dp[i-1]
	滚动变量即可。

最简逻辑模板（适合你用 Go 写 DP）
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]


滚动变量优化：
	prev, curr := 1, 2
	for i := 3; i <= n; i++ {
		prev, curr = curr, prev+curr
	}
	return curr
*/
//递归实现
//func climbStairs(n int) int {
//	if n == 1 {
//		return 1
//	} else if n == 2 {
//		return 2
//	} else {
//		return climbStairs(n-1) + climbStairs(n-2)
//	}
//}

// 动态规划迭代实现
func climbStairs(n int) int {
	if n == 1 {
		return 1
	}

	if n == 2 {
		return 2
	}

	prev, current := 1, 2

	for i := 3; i <= n; i++ {
		tmpcurrent := current
		tmpprev := prev

		current = tmpcurrent + tmpprev
		prev = tmpcurrent
	}

	return current
}

func main() {
	fmt.Println(climbStairs(44))
	climbStairsV2(3)
}

func climbStairsV2(n int) int {
	if n == 1 {
		return 1
	}

	if n == 2 {
		return 2
	}

	prev, current := 1, 2
	for i := 3; i <= n; i++ {
		current, prev = prev+current, current
	}

	return current
}
